//
//  main.c
//  ShellSort10.1
//
//  Created by zhuoooo on 2022/12/20.
//  Copyright © 2022年 zhuoooo. All rights reserved.
//  希尔／冒泡／插入／堆排序

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
#define OK 1
#define ERROR -1
typedef int Status;
typedef struct Sqlist{
    int length;
    int R[MAX_SIZE];
}Sqlist;

void CreateSqlist(Sqlist *S);//创建
void Heap_adjust(Sqlist *S, int s, int m);
Status ShellSort(Sqlist *S, int length);//shell排序
Status Bubble_Sort(Sqlist *S);//冒泡排序
Status InsertSort(Sqlist *S);//插入排序
Status HeapSort(Sqlist *S);//堆排序
void OutPutSqlist(Sqlist *S);//输出


int main(int argc, const char * argv[]) {
    int num, res = 0;
    Sqlist S;
    
    printf("1.创建\n2.shell排序\n3.冒泡排序\n4.堆排序\n5.插入排序\n6.输出\n7.退出\n");
    while(1){
        printf("请输入序号：");
        scanf("%d", &num);
        if (num == 1) {
            CreateSqlist(&S);//创建
        }
        else if (num == 2) {
            res = ShellSort(&S, S.length);//shell排序
            if (res == 1) {
                printf("shell排序成功！\n");
            }else{
                printf("shell排序失败！\n");
            }
        }
        else if (num == 3){
            res = Bubble_Sort(&S);//冒泡排序
            if (res == 1) {
                printf("冒泡排序成功！\n");
            }else{
                printf("冒泡排序失败！\n");
            }
        }
        else if (num == 4){
            res = HeapSort(&S);
            if (res == 1) {
                printf("堆排序成功！\n");
            }else{
                printf("堆排序失败！\n");
            }
        }
        else if (num == 5){
            res = InsertSort(&S);
            if (res == 1) {
                printf("插入排序成功！\n");
            }else{
                printf("插入排序失败！\n");
            }
        }
        else if (num == 6) {
            OutPutSqlist(&S);//输出
        }else if(num == 7){
            break;
        }
        else{
            printf("输入错误，请重新输入！\n");
        }
    }
    return 0;
}

void CreateSqlist(Sqlist *S){
    int i;
    
    printf("请输入要排序数的个数：");//输入要排序个数
    scanf("%d", &S->length);
    
    printf("待排序的序列是: \n");//循环输入待排序的序列
    for(i = 0; i < S->length; i++)
    {
        scanf("%d", &S->R[i]);
    }
}

Status Bubble_Sort(Sqlist *S){//冒泡排序
    int i, j;
    
    for (i = 0; i < S->length; i++) {
        for (j = 0; j < S->length-i-1; j++) {
            if (S->R[j] > S->R[j+1]) {
                int temp;
                temp = S->R[j];
                S->R[j] = S->R[j+1];
                S->R[j+1] = temp;
                
            }
        }
    }
    return OK;
}
Status ShellSort(Sqlist *S, int length)//shell排序
{
    int increment;
    int i,j;
    int temp;
    for(increment = length/2; increment > 0; increment /= 2) //用来控制步长,最后递减到1
    {
        // i从第step开始排列，应为插入排序的第一个元素
        // 可以先不动，从第二个开始排序
        for(i = increment; i < length; i++)
        {
            temp = S->R[i];
            for(j = i - increment; j >= 0 && temp < S->R[j]; j -= increment)
            {
                S->R[j + increment] = S->R[j];
            }
            S->R[j + increment] = temp; //将第一个位置填上
        }
    }
    return OK;
}
Status InsertSort(Sqlist *S){//插入排序
    int i, j, k, temp = 0;
    for(i = 1; i < S->length; i++)
    {
        temp = S->R[i];
        for(j = 0; j < i; j++)
        {
            if(temp < S->R[j])
            {
                for(k = i - 1; k >= j; k--)
                {
                    S->R[k + 1] = S->R[k];
                }
                S->R[j] = temp;
                break;
            }
        }
    }
    return OK;
}
Status HeapSort(Sqlist *S){//堆排序
    int j;
    
    for (j = S->length/2; j > 0; j--)
        Heap_adjust(S, j, S->length);   //初始建堆
    for (j = S->length; j >= 1; j--)
    {
        int temp;
        temp = S->R[0];
        S->R[0] = S->R[j];
        S->R[j] = temp;   //堆顶与最后一个交换
        Heap_adjust(S, 0, j-1);
    }
    return OK;
}
void Heap_adjust(Sqlist *S, int s, int m){
    
    int j;
    int rc = S->R[s];
    for (j = 2*s;j <= m;j *= 2)
    {
        if ((j < m)&&(S->R[j+1] > S->R[j]))//选择左、右孩子中关键字的最小者
            j++;
        if (rc < S->R[j] )
        {
            S->R[s] = S->R[j];
            s = j;
        }
        else
            break ;
    }
    S->R[s] = rc;
    
}
void OutPutSqlist(Sqlist *S){
    int i;
    printf("排序后的序列是: \n");
    for(i = 0; i < S->length; i++)
    {
        printf("%d ", S->R[i]);
    }
    printf("\n");
}
